{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Peak Element"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findPeakElement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #寻找峰值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>峰值元素是指其值严格大于左右相邻值的元素。</p>\n",
    "\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code>，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 <strong>任何一个峰值</strong> 所在位置即可。</p>\n",
    "\n",
    "<p>你可以假设&nbsp;<code>nums[-1] = nums[n] = -∞</code> 。</p>\n",
    "\n",
    "<p>你必须实现时间复杂度为 <code>O(log n)</code><em> </em>的算法来解决此问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = <code>[1,2,3,1]</code>\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>3 是峰值元素，你的函数应该返回其索引 2。</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = <code>[</code>1,2,1,3,5,6,4]\n",
    "<strong>输出：</strong>1 或 5 \n",
    "<strong>解释：</strong>你的函数可以返回索引 1，其峰值元素为 2；\n",
    "&nbsp;    或者返回索引 5， 其峰值元素为 6。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "\t<li>对于所有有效的 <code>i</code> 都有 <code>nums[i] != nums[i + 1]</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-peak-element](https://leetcode.cn/problems/find-peak-element/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-peak-element](https://leetcode.cn/problems/find-peak-element/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,1]', '[1,2,1,3,5,6,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        while left<right:\n",
    "            mid = (left+right)//2\n",
    "            if nums[mid]>nums[mid+1]:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid+1\n",
    "        return left\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: 'List[int]') -> 'int':\n",
    "        def bin_search(nums, i, j):\n",
    "            if i + 5 > j:\n",
    "                max_ = nums[i]\n",
    "                max_idx = i\n",
    "                for k in range(i + 1, j + 1):\n",
    "                    if nums[k] > max_:\n",
    "                        max_ = nums[k]\n",
    "                        max_idx = k\n",
    "                return max_idx\n",
    "            else:\n",
    "                mid=(i + j) // 2\n",
    "                if nums[mid - 1] < nums[mid] and nums[mid] > nums[mid + 1]:\n",
    "                    return mid\n",
    "                elif nums[mid - 1] < nums[mid] < nums[mid + 1]:\n",
    "                    return bin_search(nums, mid, j)\n",
    "                else:\n",
    "                    return bin_search(nums, i, mid)\n",
    "        return bin_search(nums, 0, len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.index = 0\n",
    "    def findPeak(self, nums, mid):\n",
    "        if mid > 0 and mid < len(nums)-1 and nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]:\n",
    "            self.index = mid\n",
    "            return True\n",
    "        if mid > 0 and nums[mid] < nums[mid - 1]:\n",
    "            return self.findPeak(nums, mid-1)\n",
    "        if mid < len(nums)-1 and nums[mid] < nums[mid + 1]:\n",
    "            return self.findPeak(nums, mid+1)\n",
    "        return False\n",
    "    def findPeakElement(self, nums: 'List[int]') -> 'int':\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return 0\n",
    "        if length == 2:\n",
    "            if nums[0] > nums[1]:\n",
    "                return 0\n",
    "            else:\n",
    "                return 1\n",
    "        mid = length // 2\n",
    "        if self.findPeak(nums, mid):\n",
    "            return self.index\n",
    "        else:\n",
    "            return nums.index(max(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if nums[0] > nums[1]:\n",
    "            return 0\n",
    "        if nums[n-1] > nums[n-2]:\n",
    "            return n-1\n",
    "        l = 1;h = n-2\n",
    "        while l <= h:\n",
    "            m = (l+h)>>1\n",
    "            if nums[m-1] < nums[m] > nums[m+1]:\n",
    "                return m\n",
    "            elif nums[m-1]<= nums[m] <= nums[m+1]:\n",
    "                l = m + 1\n",
    "            else:\n",
    "                h = m - 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def finder(start, end):\n",
    "            mid = (start + end) // 2\n",
    "\n",
    "            if mid > 0 and nums[mid] < nums[mid-1]:\n",
    "                return finder(start, mid - 1)\n",
    "            elif mid < end and nums[mid] < nums[mid+1]:\n",
    "                return finder(mid + 1, end)\n",
    "            else:\n",
    "                return mid\n",
    "\n",
    "        return finder(0,len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: #二分法 递归 因为已有一增,要不一直增下去边界为峰，要不先增后减则出峰)\n",
    "    def findPeakElement(self, nums):\n",
    "        n = len(nums)\n",
    "        # 处理边界情况\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if n == 2:\n",
    "            return 0 if nums[0] > nums[1] else 1\n",
    "        # 处理一般情况，n >= 3\n",
    "        i = n // 2\n",
    "        if nums[i - 1] < nums[i] and nums[i] > nums[i + 1]:\n",
    "            return i \n",
    "        elif nums[i - 1] > nums[i]:\n",
    "            # 左边必有峰值\n",
    "            return self.findPeakElement(nums[:i])\n",
    "        else:\n",
    "            # 右边必有峰值\n",
    "            return i + 1 + self.findPeakElement(nums[i + 1:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums):\n",
    "        left = 0\n",
    "        right = len(nums)-1\n",
    "        if right==0:\n",
    "            return 0\n",
    "        if nums[right]>nums[right-1]:\n",
    "            return right\n",
    "        if nums[left]>nums[left+1]:\n",
    "            return left\n",
    "        while left<right:\n",
    "            if nums[right]<nums[right-1]:\n",
    "                if nums[right-1]>nums[right-2]:\n",
    "                    return right-1\n",
    "                else:\n",
    "                    right = right - 1\n",
    "            if nums[left]<nums[left+1]:\n",
    "                if nums[left+1]>nums[left+2]:\n",
    "                    return left+1\n",
    "                else:\n",
    "                    left = left + 1\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if  len(nums) == 1:\n",
    "            return 0\n",
    "        return self.f(nums,0)\n",
    "      \n",
    "    def f(self,nums,i):\n",
    "        if i==0:\n",
    "            if nums[i]>nums[i+1]:\n",
    "                return i\n",
    "            return self.f(nums,i+1)\n",
    "        \n",
    "        if i==len(nums)-1:\n",
    "            if nums[i]>nums[i-1]:\n",
    "                return i\n",
    "            else:\n",
    "                return -1\n",
    "            \n",
    "        if nums[i]>nums[i-1] and nums[i]>nums[i+1]:\n",
    "            return i\n",
    "        else:\n",
    "            return self.f(nums,i+1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        leng = len(nums)\n",
    "        if leng ==0:\n",
    "            return 0\n",
    "        l = 0\n",
    "        r = leng -1\n",
    "        while l< r:\n",
    "            mid = (l + r +1) >>1\n",
    "            if nums[mid] > nums[mid-1]:\n",
    "                l = mid\n",
    "            else:\n",
    "                r  = mid -1\n",
    "\n",
    "        return l\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        for i in range(len(nums)):\n",
    "            if i == 0 and nums[i] > nums[i+1]:\n",
    "                return i\n",
    "            elif i == len(nums)-1 and nums[i] > nums[i-1]:\n",
    "                return i\n",
    "            elif nums[i] > nums[i+1] and nums[i] > nums[i-1]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        l,r = 0,len(nums)-1\n",
    "        while l<r:\n",
    "            mid = (l+r)//2\n",
    "            if nums[mid]>nums[mid+1]:\n",
    "                r = mid\n",
    "            else:\n",
    "                l =mid+1\n",
    "        return r\n",
    "        \n",
    "#         递归\n",
    "#         return self.search(nums,0,len(nums)-1)\n",
    "    \n",
    "#     def search(self,nums,l,r):\n",
    "#         if l==r:\n",
    "#             return l\n",
    "#         mid = (l+r)//2\n",
    "#         if nums[mid]>nums[mid+1]:\n",
    "#             return self.search(nums,l,mid)\n",
    "#         else:\n",
    "#             return self.search(nums,mid+1,r)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        left = 0\n",
    "        right = len(nums) - 1\n",
    "        while left < right:\n",
    "            d = (left + right) // 2\n",
    "            if nums[d] < nums[d+1]:\n",
    "                left = d + 1\n",
    "            else:\n",
    "                right = d\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1:\n",
    "            return 0\n",
    "        for i in range(length):\n",
    "            if (i == 0 and nums[i] > nums[i+1]) or (i == length - 1 and nums[i] > nums[i-1]):\n",
    "                return i\n",
    "            if nums[i]>nums[i-1] and nums[i] > nums[i+1]:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        for i in range(len(nums)-1):\n",
    "            if nums[i] > nums[i+1]:\n",
    "                return i \n",
    "        \n",
    "        return len(nums) - 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        left,right=0,n-1\n",
    "        if n==1:\n",
    "            return 0\n",
    "        if n==2:\n",
    "            if nums[left]<nums[right]:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        while left<right:\n",
    "            mid=left+(right-left)//2\n",
    "            if nums[mid]>nums[mid+1] and nums[mid]>nums[mid-1]:\n",
    "                return mid\n",
    "            elif nums[mid]>nums[mid+1] and nums[mid]<nums[mid-1]:\n",
    "                right=mid-1\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 1: return 0\n",
    "        left, right = 0, len(nums)-1\n",
    "        while left <= right:\n",
    "            mid = (left+right) // 2\n",
    "            if mid == 0:\n",
    "                if nums[mid] > nums[mid+1]:\n",
    "                    return mid\n",
    "                else:\n",
    "                    left = mid+1\n",
    "            elif mid == len(nums)-1:\n",
    "                if nums[mid] > nums[mid-1]:\n",
    "                    return mid\n",
    "                else:\n",
    "                    right = mid-1\n",
    "            elif nums[mid-1] < nums[mid] and nums[mid] > nums[mid+1]:\n",
    "                return mid\n",
    "            elif nums[mid] > nums[mid-1]:\n",
    "                left = mid+1\n",
    "            elif nums[mid] < nums[mid-1]:\n",
    "                right = mid-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # if n == 0:\n",
    "        #     return\n",
    "        # if n == 1:\n",
    "        #     return 0\n",
    "\n",
    "        # 基本的顺序遍历\n",
    "        # for i in range(n):\n",
    "        #     if i == 0:\n",
    "        #         if nums[i] > nums[i+1]:\n",
    "        #             return i\n",
    "        #     elif i == n-1:\n",
    "        #         if nums[i] > nums[i-1]:\n",
    "        #             return i\n",
    "        #     elif nums[i] > nums[i-1] and nums[i] > nums[i+1]:\n",
    "        #         return i\n",
    "\n",
    "        # 二分查找\n",
    "        # low, high = 0, n -1\n",
    "        # while low < high:\n",
    "        #     mid = (low + high) // 2\n",
    "        #     if mid == 0:\n",
    "        #         if nums[mid] > nums[mid+1]:\n",
    "        #             return mid\n",
    "        #     elif mid == n-1:\n",
    "        #         if nums[mid] > nums[mid-1]:\n",
    "        #             return mid\n",
    "        #     elif nums[mid] > nums[mid-1] and nums[mid] > nums[mid+1]:\n",
    "        #         return mid\n",
    "\n",
    "        #     if nums[mid] > nums[mid+1]:\n",
    "        #         high = mid - 1\n",
    "        #     elif nums[mid] < nums[mid+1]:\n",
    "        #         low = mid + 1\n",
    "\n",
    "        # return low\n",
    "\n",
    "        def binary_search(low, high):\n",
    "            if low == high:\n",
    "                return low\n",
    "            mid = (low + high) // 2\n",
    "            if nums[mid] > nums[mid+1]:\n",
    "                return binary_search(low, mid)\n",
    "            else:\n",
    "                return binary_search(mid+1, high)\n",
    "        \n",
    "        return binary_search(0, n-1)\n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        # nums = [1,2,1,3,5,6,4]\n",
    "        if len(nums) == 1: return 0\n",
    "\n",
    "        l, r = 0, len(nums)\n",
    "\n",
    "        def check(i):\n",
    "            if i == 0:\n",
    "                return i if nums[i] > nums[i+1] else -1\n",
    "            elif i == len(nums) - 1:\n",
    "                return i if nums[i] > nums[i-1] else -1\n",
    "            else:\n",
    "                return i if (nums[i] > nums[i-1] and nums[i] > nums[i+1]) else -1\n",
    "\n",
    "\n",
    "        def F(l, r):\n",
    "            # print(l, r)\n",
    "            if l + 1 >=  r:\n",
    "                if l == 0 and nums[l] > nums[r]:\n",
    "                    return l\n",
    "                if r == len(nums) - 1 and nums[r] >  nums[l]:\n",
    "                    return r\n",
    "                return -1\n",
    "                \n",
    "            mid = l + (r - l) // 2\n",
    "            # print(mid)\n",
    "            if check(mid) != -1:\n",
    "                return mid\n",
    "            \n",
    "            left = F(l, mid)\n",
    "            if left != -1:\n",
    "                return left\n",
    "            right = F(mid, r)\n",
    "            if right != -1:\n",
    "                return right\n",
    "            \n",
    "            return -1\n",
    "\n",
    "        return F(0, len(nums)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        def helper(nums, left, right):\n",
    "            while left < right:\n",
    "                mid = left + (right - left) // 2\n",
    "                if nums[mid] > nums[mid+1]:\n",
    "                    right = mid\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "        return helper(nums, 0, n-1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums) - 1  # 开区间 (-1, n-1)\n",
    "        while left < right:  # 开区间不为空\n",
    "            mid = (left + right) // 2\n",
    "            if nums[mid] > nums[mid + 1]:  # 蓝色\n",
    "                right = mid\n",
    "            else:  # 红色\n",
    "                left = mid + 1\n",
    "        return right\n",
    "        # while nums[mid]<=nums[mid+1] or nums[mid]<=nums[mid-1]:\n",
    "        #     if nums[mid]<=nums[mid+1]:\n",
    "        #         left = mid\n",
    "        #     else:\n",
    "        #         right = mid\n",
    "        #     mid = (left + right) // 2\n",
    "        #     print(mid)\n",
    "        # return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        # 第一步 \n",
    "        # 第二步\n",
    "        idx = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] > nums[idx]:\n",
    "                idx = i\n",
    "        return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        left, right = 0, len(nums) - 1\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            mid_left = nums[mid - 1] if mid - 1 >= 0 else float(\"-inf\")\n",
    "            mid_right = nums[mid + 1] if mid + 1 < len(nums) else float(\"-inf\")\n",
    "\n",
    "            if mid_left < nums[mid] and nums[mid] > mid_right:\n",
    "                return mid\n",
    "            elif mid_left < nums[mid] < mid_right:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = -1\n",
    "\n",
    "        def findPeak(left: int, right: int) -> bool:\n",
    "            if left > right:\n",
    "                return False\n",
    "\n",
    "            mid = (left + right) // 2\n",
    "            if (mid == 0 or nums[mid] > nums[mid - 1]) and (mid == n - 1 or nums[mid] > nums[mid + 1]):\n",
    "                nonlocal ans\n",
    "                ans = mid\n",
    "                return True\n",
    "\n",
    "            return findPeak(left, mid - 1) or findPeak(mid + 1, right)\n",
    "        \n",
    "        findPeak(0, n - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        if nums[1] < nums[0]:\n",
    "            return 0\n",
    "        if nums[n-2] < nums[n-1]:\n",
    "            return n-1\n",
    "        def isPeak(i):\n",
    "            if i-1>=0 and i+1 <= len(nums)-1 and nums[i] > nums[i-1] and nums[i] > nums[i+1]:\n",
    "                return True\n",
    "        def findPeak(left, right):\n",
    "            if left > right:\n",
    "                return            \n",
    "            mid = (left + right) // 2\n",
    "            if isPeak(mid):\n",
    "                return mid\n",
    "            peak1 = findPeak(left, mid-1)\n",
    "            peak2 = findPeak(mid+1, right) \n",
    "            if not (peak1 or peak2):\n",
    "                return\n",
    "            return peak1 if peak1 else peak2\n",
    "        return findPeak(0,n-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if nums[mid]>nums[mid+1]:\n",
    "                right=mid\n",
    "            else:\n",
    "                left=mid+1\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        if len(nums)<3:\n",
    "            return nums.index(max(nums))\n",
    "        left=0\n",
    "        right=len(nums)-1\n",
    "        while left<right:\n",
    "            mid=(left+right)//2\n",
    "            if nums[mid]<nums[mid+1]:\n",
    "                left=mid+1\n",
    "            else:\n",
    "                right=mid\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findPeakElement(self, nums: List[int]) -> int:\n",
    "        nums.append(-float(\"inf\"))\n",
    "        left=0\n",
    "        right=len(nums)-2\n",
    "        print(right)\n",
    "        \n",
    "        while left<=right:\n",
    "            half=(left+right)//2\n",
    "            print(half)\n",
    "            if nums[half-1]<nums[half]>nums[half+1]:\n",
    "                return half\n",
    "            if nums[half]<nums[half+1]:\n",
    "                left=half+1\n",
    "            else:\n",
    "                right=half-1\n",
    "            print(left)\n",
    "            print(right)\n",
    "        return half\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
